package com.xjj.homework.w02;

import java.util.HashMap;
import java.util.Map;

public class H1074NumberOfSubmatricesThatSumToTarget {

    public int numSubmatrixSumTarget(int[][] matrix, int target) {
        // 将同一列(也可以行)压缩到一个值上,就降维成了k子数组问题
        // 然后压缩方法为n+(n-1)+(n-2)...n^2,再求个k子数,n^2*m
        // 行数n,列数m
        int n = matrix.length;
        int m = matrix[0].length;
        // 上限固定
        int result = 0;
        for (int i = 0; i < n; i++) {
            // 一维列压缩和
            int[] sum = new int[m];
            // 下限移动,单本行也需要加
            for (int j = i; j < n; j++) {
                // 遍历单行
                for (int k = 0; k < m; k++) {
                    sum[k] += matrix[j][k];
                }
                result += subarraySum(sum, target);
            }

        }
        return result;
    }

    // 560题
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        // 不加0会漏算每个到s(i)本身满足的数
        // 比如k=2时,1,1,1会少一个[1,1]的,1,1,1,-1会少2个[1,1],[1,1,1,-1]
        map.put(0, 1);
        int sum = 0;
        int result = 0;
        for (int value : nums) {
            // 前缀和
            sum += value;
            // 此时map存的是i-1个的前缀和,所以找到满足sum-k的所有前缀和(个数)即可
            result += map.getOrDefault(sum - k, 0);
            // 将i的前缀和也加进去
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return result;
    }

}
